#include <iostream>
#include <vector>
using namespace std;

void mergeSort(vector<int>& res, int left, int right) {
	if (left < right) {
		int mid = left + ((right - left) / 2);
		mergeSort(res, left, mid);
		mergeSort(res, mid+1, right);
		merge(res, left, mid, right);
	}
}

void merge(vector<int>& res,int left,int mid,int right) {
	int *tmp = new int[right - left + 1];
	int i = left;
	int j = mid + 1;
	int index = 0;
	while (i <= mid && j <= right) {
		if (res[i] <= res[j]) {
			tmp[index++] = res[i++];
		}
		else {
			tmp[index++] = res[j++];
		}
	}
	while (i <= mid) {
		tmp[index++] = res[i++];
	}
	while (j <= right) {
		tmp[index++] = res[j++];
	}
	index = 0;
	while (left <= right) {
		res[left++] = tmp[index++];
	}
}

int main() {
	int arr[] = { 3,2,4,6,1,7,9,8 };
	vector<int> res(arr, arr + 8);
	int len = res.size();
	mergeSort(res, 0, len - 1);

	vector<int>::iterator ite = res.begin();
	for (; ite != res.end(); ite++) {
		cout << *ite << " ";
	}
	system("pause");
	return 0;
}
